package com.example.sort;

/**
 * 计数排序
 */
public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        // 找出数组中最大的数
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        // 获取最大数的位数
        int maxDigits = getMaxDigits(max);
        // 进行每一位的排序
        for (int i = 0; i < maxDigits; i++) {
            countingSortByDigit(arr, i);
        }
    }

    // 按照某一位进行排序（使用计数排序）
    private static void countingSortByDigit(int[] arr, int digit) {
        int[] count = new int[10];
        int[] output = new int[arr.length];
        // 计算每个数字在该位上的计数
        for (int num : arr) {
            int digitValue = getDigit(num, digit);
            count[digitValue]++;
        }
        // 计算累计计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        // 将数字按该位顺序放入输出数组
        for (int i = arr.length - 1; i >= 0; i--) {
            int digitValue = getDigit(arr[i], digit);
            output[count[digitValue] - 1] = arr[i];
            count[digitValue]--;
        }
        // 将排序后的数组复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    // 获取数字某一位的值
    private static int getDigit(int num, int digit) {
        return (num / (int) Math.pow(10, digit)) % 10;
    }

    // 获取最大数的位数
    private static int getMaxDigits(int num) {
        int digits = 0;
        while (num > 0) {
            digits++;
            num /= 10;
        }
        return digits;
    }

    public static void main(String[] args) {
        int[] arr = {123, 456, 789, 111, 234};
        radixSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}